COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	backtr[e82,jmc]		Proposed backtracking macro for Lisp
C00009 ENDMK
C⊗;
backtr[e82,jmc]		Proposed backtracking macro for Lisp

(backtrack ((var1 init1 update1 revert1) ...)
(move-list-variable move-generator)
(action-at-exhaution1 ... )
(termination-condition action-at-termination1 ...)
action-at-each level1 ... )

This macro generates Lisp that acts as follows:

1. The variables are initialized.  The default initialization is  nil
unless the variable is typed to be a natural number in which case
the default initialization is zero.  The initialization expressions
are evaluated and aren't just constants.

2. Making a move includes updating the variables according to the
update expressions.  When a revert takes place, the value of each variable is
computed by the corresponding revert expression.  If this expression
is omitted, then the previous value before the update is restored.

3. A list of moves is generated by the  move-generator expression at each
level unless the termination condition is true and made the value of
the move-list variable.  The other expressions mentioned can involve
this variable.

4. When the list of moves at a level is exhausted, the actions at
exhaustion are taken sequentially.

5. When the termination condition is true at a level, the
termination actions are taken sequentially.  Termination is tested
at each return to the level.

SOLVER

	A more special program (not a macro) would be a solver.  The
one that worked for the  n  queens problem already showed some
limitations in communicating information from the deeper levels
of the tree back to the primary.  Consider the following:

(defun solve (pos)
       (if (terp pos)
	   (returnform pos)
	   (solve (solve (next pos)))))

Perhaps the last line should be (solve (prepare pos (solve (next pos)))),
taking into account the possibility that it may not be convenient
to return all the information to determine what to to next.

	Let's apply this to the simple n-queens.  The first problem
is to decide on the format of  pos.

(defstruct (position)
	   list-of-moves
	   nqueens)

;;; Here seems to be a very general problem solver.  If the problem is
;;; such that it can be solved without introducing subproblems, we call
;;; it obvious, and call its solution  (obsolve problem).  Otherwise,
;;; we must generate a subproblem, solve it and solve the problem
;;; that is left after we have solved the subproblem.
(defun solve (problem)
       (if (obvious problem)
	   (obsolve problem)
	   (solve (newproblem (remembered problem)
			      (solve (subproblem problem))))))

	In the above there is no separation of facts and goals and
no separation of permanent facts from those that are recomputed
for passing to the subtask.
Note also that it is more general not to provide for lists of
subtasks, since what subtask is to be done next depends in
general on the results of previous subtasks.
When we compare this paradigm with a specific problem such as
n queens, we should remember that while an important kind of
subproblem is getting the solutions that follow from a partial
board, other kinds of problems may arise as subproblems, such as
obtaining certain auxiliary information.  When this is true,
OBVIOUS, OBSOLVE and SUBPROBLEM will all have to dispatch on cases,
and this suggests that a preliminary analysis be done, and we might
have

(defun solve (problem)
       (let ((facts (analyze problem)))
	    (if (obvious facts)
		(obsolve facts)
		(solve (newproblem (remembered facts)
				   (solve (subproblem facts)))))))

Notice that PROBLEM and FACTS are being taken as units.  Often they
will have a Cartesian product structure, and it will reduce packing
and unpacking to consider functions of the separate components.  This
will lead to a real economy when the updated values of certain variables
do not depend on all the variables.  Thus (1) is simpler than  (2)
when  OBVIOUS, OBSOLVE and  SUBPROBLEM  can be computed simply without
sharing part of the computation.